package com.czk.tree.avl;

import lombok.Data;

/**
 * 平衡二叉树的添加
 *
 * @Author:ChenZhangKun
 * @Date: 2020/7/15 20:23
 */
@SuppressWarnings("all")
public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9};
        int[] arr1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        AVLTree avlTree = new AVLTree();
        // 加入节点
        for (int i : arr1) {
            avlTree.add(new Node(i));
        }
        System.out.println(avlTree.getRoot());
        // 右子树高度
        System.out.println(avlTree.getRoot().right.height());
        // 左子树高度
        System.out.println(avlTree.getRoot().left.height());
        // avlTree.inOrderTraverse();
    }
}

class AVLTree {
    private Node root;

    // 旋转左子树
    public void leftRotate() {

    }

    public Node getRoot() {
        return this.root;
    }

    // 树高度
    public int height() {
        return root.height();
    }

    // 左子树敢赌
    public int leftHeight() {
        return root.leftHeight();
    }

    // 右子树高度
    public int rightHeight() {
        return root.rightHeight();
    }

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    // 中序遍历
    public void inOrderTraverse() {
        if (root != null) {
            root.inOrderTraverse();
        }
    }

    // 查找要删除的父节点
    public Node searchParent(int value) {
        if (root != null) {
            return root.searchParent(value);
        } else {
            return null;
        }
    }

    // 查找要删除的节点
    public Node search(int value) {
        if (root != null) {
            return root.search(value);
        } else {
            return null;
        }
    }

    // 删除节点
    public void deleteNode(int value) {
        // targetNode没有父节点的情况
        if (root.left == null && root.right == null) {
            root = null;
            return;
        }
        // 找到targetNode
        Node targetNode = root.search(value);
        if (targetNode == null) return;
        // 找到父节点
        Node nodeParent = this.searchParent(value);
        // 判断targetNode是左子节点还是右子节点
        if (targetNode.left == null && targetNode.right == null) {
            // 叶子节点
            if (nodeParent.left != null && nodeParent.left.value == value) {
                // 左子节点
                nodeParent.left = null;
            } else if (nodeParent.right != null && nodeParent.right.value == value) {
                nodeParent.right = null;
            }
        } else if (targetNode.left != null && targetNode.right != null) {
            // 拥有两个子树
            // 删除最小值
            int i = this.deleteRightTreeMin(targetNode.right);
            targetNode.value = i;
        } else {
            // 拥有一个子树
            // 只有左子节点
            if (targetNode.left != null) {
                // 如果targetNode是parent的左子节点
                if (nodeParent != null && nodeParent.left.value == value) {
                    nodeParent.left = targetNode.left;
                } else if (nodeParent != null && nodeParent.right.value == value) {
                    nodeParent.right = targetNode.left;
                } else {
                    // 根节点为空的情况
                    root = targetNode.left;
                }
            } else {
                // 删除的节点是右子节点
                if (nodeParent != null && nodeParent.left.value == value) {
                    nodeParent.left = targetNode.right;
                } else if (nodeParent != null) {
                    nodeParent.right = targetNode.right;
                } else {
                    // 根节点为空的情况
                    root = targetNode.right;
                }
            }
        }

    }

    /**
     * @param node 查找的节点
     * @return 该树的最小值
     */
    public int deleteRightTreeMin(Node node) {
        Node target = node;
        while (target.left != null) {
            target = target.left;
        }
        // 删除最小节点
        this.deleteNode(target.value);
        return target.value;
    }
}

@Data
class Node {
    // 值
    int value;
    // 左节点
    Node left;
    // 右节点
    Node right;

    // 旋转左子树
    public void leftRotate() {
        // 创建新节点，保存当前根节点的值
        Node newNode = new Node(value);
        // 把新节点的左子树设置成当前节点的左子树
        newNode.left = this.left;
        // 把新节点的右子树设置成你带过去节点右子树的左子树
        newNode.right = this.right.left;
        // 把当前节点的值替换成右子节点的值
        value = this.right.value;
        // 把当前节点的右子树设置成当前节点的右子树的右子树
        this.right = right.right;
        // 把当前节点的左子树左子节点设置成新的节点
        left = newNode;
    }

    public void rightRotate() {
        // 创建新节点，保存当前根节点的值
        Node newNode = new Node(value);
        //
        newNode.right = this.right;
        //
        newNode.left = left.right;
        //
        value = left.value;
        //
        left = left.left;
        //
        right = newNode;
    }


    // 返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        } else {
            return left.height();
        }
    }

    // 返回右子树的敢赌
    public int rightHeight() {
        if (right == null) {
            return 0;
        } else {
            return right.height();
        }
    }

    // 返回以该节点为根节点树的高度
    public int height() {
        // 递归求树高度经典解答
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }



    // 查找节点
    public Node search(int value) {
        if (value == this.value) {
            // 找到该节点
            return this;
        } else if (value < this.value) {
            // 不是当前节点,向左子树递归查找
            if (this.left != null) {
                this.left.search(value);
            } else {
                // 向右递归查找
                if (this.right != null) {
                    this.right.search(value);
                }
            }
        }
        return null;
    }

    // 查找要删除节点的父节点
    public Node searchParent(int value) {
        // 左节点不为空或者右节点不为空
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            // 返回值
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                // 返回值
                return this.right.searchParent(value);
            }
        }
        return null;
    }

    public Node(int value) {
        this.value = value;
    }

    // 添加节点
    // 递归的形式添加节点，需要满足二叉排序树的特点
    public void add(Node node) {
        // 节点是否为空
        if (node == null) {
            return;
        }
        // 判断传入的值和当前节点的值关系
        if (node.value < this.value) {
            // 左节点为空，挂载在左节点
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else if (this.value < node.value) {
            // 添加到右节点
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        // 当添加完一个节点后，右子树的高度比左子树的高度大于1，则需要左旋转
        if (this.rightHeight() - this.leftHeight() > 1) {
            // 右子树的左子树的高度大于左子树的高度 右子树左子树的高度大于了左子树的盖度 先右旋在左旋的双旋
            if (right != null && right.left != null && right.left.height() > left.height()) {
                // 先对右子节点进行右旋转
                right.rightRotate();
            }
            // 左旋转
            this.leftRotate();
            return;
        }

        if (this.leftHeight() - this.rightHeight() > 1) {
            // 左子节点的右子树高度大于右子节点的高度 ，此时需要进行双旋转
            if (left != null && left.right.height() > right.height()) {
                // 先对左子树进行左旋转
                left.leftRotate();
            }
            // 右旋转
            this.rightRotate();
        }
    }

    // 中序遍历
    public void inOrderTraverse() {
        if (this.left != null) {
            this.left.inOrderTraverse();
        }
        System.out.println(this);
        if (this.right != null)
            this.right.inOrderTraverse();
    }
}
